package com.honeywen.mymvc.leetcode;

import lombok.val;

import java.util.HashSet;
import java.util.Set;

/**
 * 82. 删除排序链表中的重复元素 II
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/description/
 * <p>
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2->3->3->4->4->5
 * 输出: 1->2->5
 * 示例 2:
 * <p>
 * 输入: 1->1->1->2->3
 * 输出: 2->3
 *
 * @author wangwei
 * @date 2018/11/24 下午3:13
 */
public class DuplicateListMedium {

    public static void main(String[] args) {
        // 1,1,2,3,3

        ListNode head = new ListNode(1);
        ListNode n1 = new ListNode(2);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(2);
        ListNode n4 = new ListNode(4);
        head.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;

        printListNode(head);

        printListNode(deleteDuplicates(head));
        printListNode(deleteDuplicates4(head));

    }


    public static ListNode deleteDuplicates4(ListNode head) {

        ListNode first = new ListNode(0);
        first.next = head;

        ListNode node = head;
        boolean duplicate = false;

        head = first;

        while (node != null && node.next != null) {

            if (!duplicate && node.val == node.next.val) {
                duplicate = true;
                node = node.next;
                continue;
            }

            if (duplicate && node.val != node.next.val) {
                first.next = node.next;
                node = node.next;
                continue;
            }

            if (!duplicate) {
                first = node;
                node = node.next;
            }
        }

        if (duplicate) {
            first.next = null;
        }

        return head.next;
    }

    public static ListNode deleteDuplicates(ListNode head) {

        ListNode tail = new ListNode(0);
        tail.next = head;

        head = tail;
        boolean flag = false;


        for (ListNode node = head.next; node != null && node.next != null; node = node.next) {

            if (!flag && node.val == node.next.val) {

                flag = true;
                continue;
            }
            if (flag && node.val != node.next.val) {
                flag = false;
                tail.next = node.next;

                continue;
            }

            if (!flag) {
                tail = node;
            }
        }

        if (flag) {
            tail.next = null;
        }
        return head.next;


    }


    public static ListNode deleteDuplicates3(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        // 1. 记录重复值， 2.删除重复值， 3.从第二个开始
        ListNode node = head;
        ListNode prev = node;

        int duplicate = head.val;

        boolean firstDuplicate = false;
        if (head.next != null && head.val == head.next.val) {
            firstDuplicate = true;
        }


        while (node != null && node.next != null) {

            if (node.val == node.next.val) {
                duplicate = node.val;

                node = node.next.next;
                prev.next = node;
            } else {
                if (node.val == duplicate) {
                    prev.next = node.next;
                    node = node.next;
                } else {

                    prev = node;
                    node = node.next;
                }
            }

        }


        // 全重复
        if (node != null && node.val == head.val) {
            return null;
        }
        // 第一个是否重复, 第一个重复
        if (firstDuplicate) {
            return head.next;
        }


        return head;


    }


    private static void printListNode(ListNode listNode) {
        while (listNode != null) {
            System.out.print(listNode.val + "->");
            listNode = listNode.next;
        }
        System.out.println();
    }

    public static ListNode deleteDuplicates2(ListNode head) {

        ListNode flag = head;

        while (head != null && head.next != null) {

            if (head.val == head.next.val) {
                // 删除2
                head.next = head.next.next;

            } else {
                // 往前推进，
                head = head.next;
            }

        }


        return flag;

    }


}
